原文題目

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

題目摘要

1. 給定一個樓梯，共有 n 階。
2. 每次可以選擇爬 1 階或 2 階，問共有多少種不同的方式爬到樓梯頂端。

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解題思路

1. 問題拆解：
   • 假設你現在在第 n 階，之前一步可能從 n-1 階爬上來，也可能是從 n-2 階爬上來。這意味著你到達第 n 階的方式總數等於你到達 n-1 階的方式總數加上你到達 n-2 階的方式總數。
   • 因此，問題可以拆分成一個遞迴的關係：f(n) = f(n-1) + f(n-2)，這跟斐波那契數列的定義是一樣的。
2. 基礎情況：
   • 當你只有一階時，只有一種方式，就是直接爬一階。
   • 當你有兩階時，則有兩種方式，分別是：一次爬兩階或分兩次各爬一階。
3. 總結：
   • 計算每一階的方式數，逐步累加即可，直到到達第 n 階。
   • 可以使用遞迴或動態規劃來實現，但動態規劃能夠更有效地解決這類問題，因為它避免了重複計算。

程式碼

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        //基礎情況：當今天n<3時，output都會恰好等於n
        if(n<3){
            return n;
        }
        //計算dp[3]前需要先宣告dp[1]、dp[2]
        dp[1]=1;
        dp[2]=2;
        //n>2以後只須根據前兩個加總即可算出所有步數可能
        for(int i=3; i<n+1; i++){
            dp[i]=dp[i-2]+dp[i-1];
        }
        return dp[n];
    }
}

結論： 爬樓梯問題是一個很好的練習動態規劃的範例，它告訴我們如何把複雜的問題拆解成簡單的子問題，進而找到解決方案。實際上，這個問題和斐波那契數列有很多相似之處，因為每一步的選擇都取決於前面兩步的結果。生活中，我們也常面對需要分步完成的任務，這種問題就像是提前計劃每一步，讓我們能夠更有效率地達成目標。掌握了這種思路，不僅能在程式設計中受益，也能在日常生活的規劃和決策中發揮作用。